#include<iostream>
#include<vector>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

/*
 *二分查找循环实现
 */
int BinarySearch(const vector<int> &nums,int target)
{
    decltype(nums.size()) lo=0;
    decltype(nums.size()) hi=nums.size()-1;
    while(lo<=hi){
        int mid=(lo+hi)/2;//取中间数
        if(nums[mid]==target)//找到
            return mid;
        if(nums[mid]>target)
            hi=mid-1;
        else
            lo=mid+1;
    }
    return -1;//没找到
}

/*
 *二分查找递归实现
 */
int BinarySearch(const vector<int> &nums,int target,decltype(nums.size()) lo,decltype(nums.size()) hi)
{
   if(lo>hi)
        return -1;
    int mid=(hi+lo)/2;
    if(nums[mid]==target)
        return mid;
    if(nums[mid]>target)
        return BinarySearch(nums,target,lo,mid-1);
    if(nums[mid]<target)
        return BinarySearch(nums,target,mid+1,hi);
}
